import bean.ListNode;

import java.util.PriorityQueue;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 困难
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * @since 2023-08-28 15:34
 */
public class _023合并k个升序链表 {
    //By me
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode[] heads = new ListNode[lists.length];
        ListNode newHead = new ListNode();
        ListNode p = newHead;
        for(int i = 0; i < lists.length; i++){
            heads[i] = lists[i];
        }
        int index = 0, minVal = Integer.MAX_VALUE;
        while(true){
            //find min
            index = -1;
            minVal = Integer.MAX_VALUE;
            for(int i = 0; i < lists.length; i++){
                if(heads[i] != null && heads[i].val < minVal){
                    index = i;
                    minVal = heads[i].val;
                }
            }
            if(index == -1){
                break;
            }
            //归并
            p.next = new ListNode(heads[index].val);
            heads[index] = heads[index].next;
            p = p.next;
        }
        return newHead.next;
    }
    //使用优先队列
    static class Item implements Comparable<Item> {
        int val;
        ListNode ptr;

        Item(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        public int compareTo(Item status2) {
            return this.val - status2.val;
        }
    }

    PriorityQueue<Item> queue = new PriorityQueue<>();

    public ListNode mergeKLists1(ListNode[] lists) {
        for (ListNode node: lists) {
            if (node != null) {
                queue.offer(new Item(node.val, node));
            }
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while (!queue.isEmpty()) {
            Item f = queue.poll();
            tail.next = f.ptr;
            tail = tail.next;
            if (f.ptr.next != null) {
                queue.offer(new Item(f.ptr.next.val, f.ptr.next));
            }
        }
        return head.next;
    }
}
